package day_2022_7_to_8.day48;

/**
 * 45. 跳跃游戏 II
 * @author haomin
 * @date 2022/07/20 10:11
 **/
public class Day5_1_Num45_Jump {
// 重点：在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，
// 否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，
// 我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。

    // 方法一：动态规划
    class Solution1 {
        public int jump(int[] nums) {
            int[] dp = new int[nums.length];
            // 初始化数组
            dp[0] = 0;
            for(int i = 1;i < dp.length;i++){
                dp[i] = Integer.MAX_VALUE;
            }

            // 遍历数组
            for(int i = 0;i < nums.length;i++){
                // 遍历每个元素，判读能向后走几步
                for(int j = 1;j <= nums[i];j++){
                    // （当前可向后走的步数+当前位置索引）大于数组长度，遍历结束
                    if(i + j >= nums.length){
                        return dp[dp.length-1];
                    }
                    // 覆盖较小值
                    dp[i+j] = Math.min(dp[i + j],dp[i]+1);
                }
            }
            return dp[dp.length-1];
        }
    }

    // 方法二：贪心 反向查找出发位置
    class Solution2 {
        public int jump(int[] nums) {
            int position = nums.length-1;
            int steps = 0;
            while(position > 0){
                for(int i = 0;i < position;i++){
                    if(i + nums[i] >= position){
                        position = i;
                        steps++;
                    }
                }
            }
            return steps;
        }
    }

    // 方法三：贪心 正向查找可到达的最大位置
    class Solution {
        public int jump(int[] nums) {
            // 当前跳跃能到达最远位置
            int far_position = 0;
            // 上次跳跃后的位置
            int end_position = 0;
            // 当前开始跳跃位置
            int now_position = 0;
            int steps = 0;
            while(end_position < nums.length-1){
                far_position = Math.max(far_position, now_position + nums[now_position]);
                // 当 当前开始跳跃位置 走到上次跳跃后的位置，
                // 更新当前跳跃能到达最远位置
                if(now_position == end_position){
                    end_position = far_position;
                    steps++;
                }
                now_position++;
            }
            return steps;
        }
    }
}